home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / jpsrc2.zip / JQUANT1.C < prev    next >
C/C++ Source or Header  |  1991-12-08  |  13KB  |  389 lines
  1. /*
  2.  * jquant1.c
  3.  *
  4.  * Copyright (C) 1991, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains 1-pass color quantization (color mapping) routines.
  9.  * These routines are invoked via the methods color_quantize
  10.  * and color_quant_init/term.
  11.  */
  12.  
  13. #include "jinclude.h"
  14.  
  15. #ifdef QUANT_1PASS_SUPPORTED
  16.  
  17.  
  18. /*
  19.  * This implementation is a fairly dumb, quick-and-dirty quantizer;
  20.  * it's here mostly so that we can start working on colormapped output formats.
  21.  *
  22.  * We quantize to a color map that is selected in advance of seeing the image;
  23.  * the map depends only on the requested number of colors (at least 8).
  24.  * The map consists of all combinations of Ncolors[j] color values for each
  25.  * component j; we choose Ncolors[] based on the requested # of colors.
  26.  * We always use 0 and MAXJSAMPLE in each color (hence the minimum 8 colors).
  27.  * Any additional color values are equally spaced between these limits.
  28.  *
  29.  * The result almost always needs dithering to look decent.
  30.  */
  31.  
  32. #define MAX_COMPONENTS 4    /* max components I can handle */
  33.  
  34. static int total_colors;    /* Number of distinct output colors */
  35. static int Ncolors[MAX_COMPONENTS]; /* # of values alloced to each component */
  36. /* total_colors is the product of the Ncolors[] values */
  37.  
  38. static JSAMPARRAY colormap;    /* The actual color map */
  39. /* colormap[i][j] = value of i'th color component for output pixel value j */
  40.  
  41. static JSAMPARRAY colorindex;    /* Precomputed mapping for speed */
  42. /* colorindex[i][j] = index of color closest to pixel value j in component i,
  43.  * premultiplied so that the correct mapped value for a pixel (r,g,b) is:
  44.  *   colorindex[0][r] + colorindex[1][g] + colorindex[2][b]
  45.  */
  46.  
  47.  
  48. /* Declarations for Floyd-Steinberg dithering.
  49.  * Errors are accumulated into the arrays evenrowerrs[] and oddrowerrs[],
  50.  * each of which have #colors * (#columns + 2) entries (so that first/last
  51.  * pixels need not be special cases).  These have resolutions of 1/16th of
  52.  * a pixel count.  The error at a given pixel is propagated to its unprocessed
  53.  * neighbors using the standard F-S fractions,
  54.  *        ...    (here)    7/16
  55.  *        3/16    5/16    1/16
  56.  * We work left-to-right on even rows, right-to-left on odd rows.
  57.  *
  58.  * Note: on a wide image, we might not have enough room in a PC's near data
  59.  * segment to hold the error arrays; so they are allocated with alloc_medium.
  60.  */
  61.  
  62. #ifdef EIGHT_BIT_SAMPLES
  63. typedef INT16 FSERROR;        /* 16 bits should be enough */
  64. #else
  65. typedef INT32 FSERROR;        /* may need more than 16 bits? */
  66. #endif
  67.  
  68. typedef FSERROR FAR *FSERRPTR;    /* pointer to error array (in FAR storage!) */
  69.  
  70. static FSERRPTR evenrowerrs, oddrowerrs; /* current-row and next-row errors */
  71. static boolean on_odd_row;    /* flag to remember which row we are on */
  72.  
  73.  
  74. /*
  75.  * Initialize for one-pass color quantization.
  76.  */
  77.  
  78. METHODDEF void
  79. color_quant_init (decompress_info_ptr cinfo)
  80. {
  81.   int max_colors = cinfo->desired_number_of_colors;
  82.   int i,j,k, ntc, nci, blksize, blkdist, ptr, val;
  83.  
  84.   if (cinfo->color_out_comps > MAX_COMPONENTS)
  85.     ERREXIT1(cinfo->emethods, "Cannot quantize more than %d color components",
  86.          MAX_COMPONENTS);
  87.   if (max_colors > (MAXJSAMPLE+1))
  88.     ERREXIT1(cinfo->emethods, "Cannot request more than %d quantized colors",
  89.         MAXJSAMPLE+1);
  90.  
  91.   /* Initialize to 2 color values for each component */
  92.   total_colors = 1;
  93.   for (i = 0; i < cinfo->color_out_comps; i++) {
  94.     Ncolors[i] = 2;
  95.     total_colors *= 2;
  96.   }
  97.   if (total_colors > max_colors)
  98.     ERREXIT1(cinfo->emethods, "Cannot quantize to fewer than %d colors",
  99.          total_colors);
  100.  
  101.   /* Increase the number of color values until requested limit is reached. */
  102.   /* Note that for standard RGB color space, we will have at least as many */
  103.   /* red values as green, and at least as many green values as blue. */
  104.   i = 0;            /* component index to increase next */
  105.   /* test calculates ntc = new total_colors if Ncolors[i] is incremented */
  106.   while ((ntc = (total_colors / Ncolors[i]) * (Ncolors[i]+1)) <= max_colors) {
  107.     Ncolors[i]++;        /* OK, apply the increment */
  108.     total_colors = ntc;
  109.     i++;            /* advance to next component */
  110.     if (i >= cinfo->color_out_comps) i = 0;
  111.   }
  112.  
  113.   /* Report selected color counts */
  114.   if (cinfo->color_out_comps == 3)
  115.     TRACEMS4(cinfo->emethods, 1, "Quantizing to %d = %d*%d*%d colors",
  116.          total_colors, Ncolors[0], Ncolors[1], Ncolors[2]);
  117.   else
  118.     TRACEMS1(cinfo->emethods, 1, "Quantizing to %d colors", total_colors);
  119.  
  120.   /* Allocate and fill in the colormap and color index. */
  121.   /* The colors are ordered in the map in standard row-major order, */
  122.   /* i.e. rightmost (highest-indexed) color changes most rapidly. */
  123.  
  124.   colormap = (*cinfo->emethods->alloc_small_sarray)
  125.         ((long) total_colors, (long) cinfo->color_out_comps);
  126.   colorindex = (*cinfo->emethods->alloc_small_sarray)
  127.         ((long) (MAXJSAMPLE+1), (long) cinfo->color_out_comps);
  128.  
  129.   /* blksize is number of adjacent repeated entries for a component */
  130.   /* blkdist is distance between groups of identical entries for a component */
  131.   blkdist = total_colors;
  132.  
  133.   for (i = 0; i < cinfo->color_out_comps; i++) {
  134.     /* fill in colormap entries for i'th color component */
  135.     nci = Ncolors[i];        /* # of distinct values for this color */
  136.     blksize = blkdist / nci;
  137.     for (j = 0; j < nci; j++) {
  138.       /* Compute j'th output value (out of nci) for component */
  139.       val = (j * MAXJSAMPLE + (nci-1)/2) / (nci-1);
  140.       /* Fill in all colormap entries that have this value of this component */
  141.       for (ptr = j * blksize; ptr < total_colors; ptr += blkdist) {
  142.     /* fill in blksize entries beginning at ptr */
  143.     for (k = 0; k < blksize; k++)
  144.       colormap[i][ptr+k] = (JSAMPLE) val;
  145.       }
  146.     }
  147.     blkdist = blksize;        /* blksize of this color is blkdist of next */
  148.  
  149.     /* fill in colorindex entries for i'th color component */
  150.     for (j = 0; j <= MAXJSAMPLE; j++) {
  151.       /* compute index of color closest to pixel value j */
  152.       val = (j * (nci-1) + CENTERJSAMPLE) / MAXJSAMPLE;
  153.       /* premultiply so that no multiplication needed in main processing */
  154.       colorindex[i][j] = (JSAMPLE) (val * blksize);
  155.     }
  156.   }
  157.  
  158.   /* Pass the colormap to the output module.  Note that the output */
  159.   /* module is allowed to save this pointer and use the map during */
  160.   /* any put_pixel_rows call! */
  161.   (*cinfo->methods->put_color_map) (cinfo, total_colors, colormap);
  162.  
  163.   /* Allocate Floyd-Steinberg workspace if necessary */
  164.   if (cinfo->use_dithering) {
  165.     size_t arraysize = (cinfo->image_width + 2L) * cinfo->color_out_comps
  166.                * SIZEOF(FSERROR);
  167.  
  168.     evenrowerrs = (FSERRPTR) (*cinfo->emethods->alloc_medium) (arraysize);
  169.     oddrowerrs  = (FSERRPTR) (*cinfo->emethods->alloc_medium) (arraysize);
  170.     /* we only need to zero the forward contribution for current row. */
  171.     jzero_far((void FAR *) evenrowerrs, arraysize);
  172.     on_odd_row = FALSE;
  173.   }
  174.  
  175. }
  176.  
  177.  
  178. /*
  179.  * Map some rows of pixels to the output colormapped representation.
  180.  */
  181.  
  182. METHODDEF void
  183. color_quantize (decompress_info_ptr cinfo, int num_rows,
  184.         JSAMPIMAGE input_data, JSAMPARRAY output_data)
  185. /* General case, no dithering */
  186. {
  187.   register int pixcode, ci;
  188.   register long col;
  189.   register int row;
  190.   register long widthm1 = cinfo->image_width - 1;
  191.   register int nc = cinfo->color_out_comps;  
  192.  
  193.   for (row = 0; row < num_rows; row++) {
  194.     for (col = widthm1; col >= 0; col--) {
  195.       pixcode = 0;
  196.       for (ci = 0; ci < nc; ci++) {
  197.     pixcode += GETJSAMPLE(colorindex[ci]
  198.                   [GETJSAMPLE(input_data[ci][row][col])]);
  199.       }
  200.       output_data[row][col] = (JSAMPLE) pixcode;
  201.     }
  202.   }
  203. }
  204.  
  205.  
  206. METHODDEF void
  207. color_quantize3 (decompress_info_ptr cinfo, int num_rows,
  208.          JSAMPIMAGE input_data, JSAMPARRAY output_data)
  209. /* Fast path for color_out_comps==3, no dithering */
  210. {
  211.   register int pixcode;
  212.   register JSAMPROW ptr0, ptr1, ptr2, ptrout;
  213.   register long col;
  214.   register int row;
  215.   register long width = cinfo->image_width;
  216.  
  217.   for (row = 0; row < num_rows; row++) {
  218.     ptr0 = input_data[0][row];
  219.     ptr1 = input_data[1][row];
  220.     ptr2 = input_data[2][row];
  221.     ptrout = output_data[row];
  222.     for (col = width; col > 0; col--) {
  223.       pixcode  = GETJSAMPLE(colorindex[0][GETJSAMPLE(*ptr0++)]);
  224.       pixcode += GETJSAMPLE(colorindex[1][GETJSAMPLE(*ptr1++)]);
  225.       pixcode += GETJSAMPLE(colorindex[2][GETJSAMPLE(*ptr2++)]);
  226.       *ptrout++ = (JSAMPLE) pixcode;
  227.     }
  228.   }
  229. }
  230.  
  231.  
  232. METHODDEF void
  233. color_quantize_dither (decompress_info_ptr cinfo, int num_rows,
  234.                JSAMPIMAGE input_data, JSAMPARRAY output_data)
  235. /* General case, with Floyd-Steinberg dithering */
  236. {
  237.   register int pixcode, ci;
  238.   register FSERROR val;
  239.   register FSERRPTR thisrowerr, nextrowerr;
  240.   register long col;
  241.   register int row;
  242.   register long width = cinfo->image_width;
  243.   register int nc = cinfo->color_out_comps;  
  244.  
  245.   for (row = 0; row < num_rows; row++) {
  246.     if (on_odd_row) {
  247.       /* work right to left in this row */
  248.       thisrowerr = oddrowerrs + width*nc;
  249.       nextrowerr = evenrowerrs + width*nc;
  250.       for (ci = 0; ci < nc; ci++) /* need only initialize this one entry */
  251.     nextrowerr[ci] = 0;
  252.       for (col = width - 1; col >= 0; col--) {
  253.     /* select the output pixel value */
  254.     pixcode = 0;
  255.     for (ci = 0; ci < nc; ci++) {
  256.       /* compute pixel value + accumulated error */
  257.       val = (((FSERROR) GETJSAMPLE(input_data[ci][row][col])) << 4)
  258.         + thisrowerr[ci];
  259.       if (val <= 0) val = 0; /* must watch for range overflow! */
  260.       else {
  261.         val += 8;        /* divide by 16 with proper rounding */
  262.         val >>= 4;
  263.         if (val > MAXJSAMPLE) val = MAXJSAMPLE;
  264.       }
  265.       thisrowerr[ci] = val;    /* save for error propagation */
  266.       pixcode += GETJSAMPLE(colorindex[ci][val]);
  267.     }
  268.     output_data[row][col] = (JSAMPLE) pixcode;
  269.     /* propagate error to adjacent pixels */
  270.     for (ci = 0; ci < nc; ci++) {
  271.       val = thisrowerr[ci] - (FSERROR) GETJSAMPLE(colormap[ci][pixcode]);
  272.       thisrowerr[ci-nc] += val * 7;
  273.       nextrowerr[ci+nc] += val * 3;
  274.       nextrowerr[ci   ] += val * 5;
  275.       nextrowerr[ci-nc]  = val; /* not +=, since not initialized yet */
  276.     }
  277.     thisrowerr -= nc;    /* advance error ptrs to next pixel entry */
  278.     nextrowerr -= nc;
  279.       }
  280.       on_odd_row = FALSE;
  281.     } else {
  282.       /* work left to right in this row */
  283.       thisrowerr = evenrowerrs + nc;
  284.       nextrowerr = oddrowerrs + nc;
  285.       for (ci = 0; ci < nc; ci++) /* need only initialize this one entry */
  286.     nextrowerr[ci] = 0;
  287.       for (col = 0; col < width; col++) {
  288.     /* select the output pixel value */
  289.     pixcode = 0;
  290.     for (ci = 0; ci < nc; ci++) {
  291.       /* compute pixel value + accumulated error */
  292.       val = (((FSERROR) GETJSAMPLE(input_data[ci][row][col])) << 4)
  293.         + thisrowerr[ci];
  294.       if (val <= 0) val = 0; /* must watch for range overflow! */
  295.       else {
  296.         val += 8;        /* divide by 16 with proper rounding */
  297.         val >>= 4;
  298.         if (val > MAXJSAMPLE) val = MAXJSAMPLE;
  299.       }
  300.       thisrowerr[ci] = val;    /* save for error propagation */
  301.       pixcode += GETJSAMPLE(colorindex[ci][val]);
  302.     }
  303.     output_data[row][col] = (JSAMPLE) pixcode;
  304.     /* propagate error to adjacent pixels */
  305.     for (ci = 0; ci < nc; ci++) {
  306.       val = thisrowerr[ci] - (FSERROR) GETJSAMPLE(colormap[ci][pixcode]);
  307.       thisrowerr[ci+nc] += val * 7;
  308.       nextrowerr[ci-nc] += val * 3;
  309.       nextrowerr[ci   ] += val * 5;
  310.       nextrowerr[ci+nc]  = val; /* not +=, since not initialized yet */
  311.     }
  312.     thisrowerr += nc;    /* advance error ptrs to next pixel entry */
  313.     nextrowerr += nc;
  314.       }
  315.       on_odd_row = TRUE;
  316.     }
  317.   }
  318. }
  319.  
  320.  
  321. /*
  322.  * Finish up at the end of the file.
  323.  */
  324.  
  325. METHODDEF void
  326. color_quant_term (decompress_info_ptr cinfo)
  327. {
  328.   /* We can't free the colormap until now, since output module may use it! */
  329.   (*cinfo->emethods->free_small_sarray)
  330.         (colormap, (long) cinfo->color_out_comps);
  331.   (*cinfo->emethods->free_small_sarray)
  332.         (colorindex, (long) cinfo->color_out_comps);
  333.   if (cinfo->use_dithering) {
  334.     (*cinfo->emethods->free_medium) ((void FAR *) evenrowerrs);
  335.     (*cinfo->emethods->free_medium) ((void FAR *) oddrowerrs);
  336.   }
  337. }
  338.  
  339.  
  340. /*
  341.  * Prescan some rows of pixels.
  342.  * Not used in one-pass case.
  343.  */
  344.  
  345. METHODDEF void
  346. color_quant_prescan (decompress_info_ptr cinfo, int num_rows,
  347.              JSAMPIMAGE image_data)
  348. {
  349.   ERREXIT(cinfo->emethods, "Should not get here!");
  350. }
  351.  
  352.  
  353. /*
  354.  * Do two-pass quantization.
  355.  * Not used in one-pass case.
  356.  */
  357.  
  358. METHODDEF void
  359. color_quant_doit (decompress_info_ptr cinfo, quantize_caller_ptr source_method)
  360. {
  361.   ERREXIT(cinfo->emethods, "Should not get here!");
  362. }
  363.  
  364.  
  365. /*
  366.  * The method selection routine for 1-pass color quantization.
  367.  */
  368.  
  369. GLOBAL void
  370. jsel1quantize (decompress_info_ptr cinfo)
  371. {
  372.   if (! cinfo->two_pass_quantize) {
  373.     cinfo->methods->color_quant_init = color_quant_init;
  374.     if (cinfo->use_dithering) {
  375.       cinfo->methods->color_quantize = color_quantize_dither;
  376.     } else {
  377.       if (cinfo->color_out_comps == 3)
  378.     cinfo->methods->color_quantize = color_quantize3;
  379.       else
  380.     cinfo->methods->color_quantize = color_quantize;
  381.     }
  382.     cinfo->methods->color_quant_prescan = color_quant_prescan;
  383.     cinfo->methods->color_quant_doit = color_quant_doit;
  384.     cinfo->methods->color_quant_term = color_quant_term;
  385.   }
  386. }
  387.  
  388. #endif /* QUANT_1PASS_SUPPORTED */
  389.